package vj.recursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class CrossProduct {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<List<Integer>> input = new ArrayList<List<Integer>>();
		List<Integer> l1 = new ArrayList<Integer>();
		l1.add(1);l1.add(2);
		List<Integer> l2 = new ArrayList<Integer>();
		l2.add(3);l2.add(4);l2.add(5);
		List<Integer> l3 = new ArrayList<Integer>();
		l3.add(6);l3.add(7);l3.add(8);
		List<Integer> l4 = new ArrayList<Integer>();
		l4.add(9);l4.add(10);
		List<List<Integer>>  res = new ArrayList<List<Integer>> ();
		input.add(l1);
		input.add(l2);
		input.add(l3);
		input.add(l4);
		crossProd(input, res);
		for(List<Integer> l : res) {
			System.out.print("{");
			for(int k = 0; k < l.size() - 1; k++) {
				System.out.print(l.get(k)+ ",");
			}
			System.out.print(l.get(l.size() - 1));
			System.out.print("},");
		}
	}
	
	public static void crossProd(List<List<Integer>> input, List<List<Integer>>  res) {
		crossProdRec(input, new HashSet<Integer>(), 0, res);
	
	}
	
	public static void crossProdRec(List<List<Integer>> lists, Set<Integer> sofar, int i, List<List<Integer>> res) {
		
		List<Integer> cur = lists.get(i);
		//Set<Set<Integer>> res = new HashSet<Set<Integer>>();
		if(i == lists.size() - 1) {// last list
			for(Integer k : cur) {
				List<Integer> s = new ArrayList<Integer>(sofar);
				s.add(k);
				res.add(s);
			}
			return;
		}
		for(Integer k : cur) {
			sofar.add(k);
			crossProdRec(lists, sofar, i + 1, res);
			//res.add(sub);
			sofar.remove(k);
		}
	}

}
